package three;

public class A048 {


    //最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //1.两侧 -- 递归在两边都找到了，返回root -- 对应第一个if
        //2.同一侧,其中一个为根  返回这个根 -- 对应2-3的if

        if(root==null) return null;
        if(root==p || root==q) return root;

        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);

        if(leftNode!=null && rightNode!=null) return root;
        else if(leftNode!=null && rightNode==null) return leftNode;
        else return rightNode;
    }

}
